package com.base.dataStructure.priorityqueue;

import com.base.dataStructure.queue.Queue;

/**
 * @Author: hdhao
 * @Create: 2023/4/2 - 17:44
 * @Version: v1.0
 */
//基于无序数组实现的优先级队列
//优先级队列:一端进,一端出 按优先级出队
@SuppressWarnings("all")
public class PriorityQueue1<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;//数组中元素个数的大小,也可以把它当做尾指针

    public PriorityQueue1(int capacity) {
        this.array = new Priority[capacity];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        array[size] = e;
        size++;
        return true;
    }

    /**
     * 返回优先级最高的索引值
     * @return
     */
    private int selectMax(){
        int max = 0;
        for (int i = 1; i < size; i++) {
            if (array[i].priority() > array[max].priority()) {
                max = i;
            }
        }
        return max;
    }
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        E e = (E) array[max];
        remove(max);
        return e;
    }

    private void remove(int index) {
        if (index < size - 1) {
            //移动
            System.arraycopy(array, index + 1,
                    array, index, size - 1 - index);
        }
        size--;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();

        return (E) array[max];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
